// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type TreeNode struct {
	Data  int
	Left  *TreeNode
	Right *TreeNode
}

func deepestChildTreeSum(root *TreeNode) int {
	maxLevel, sum := 0, 0
	dfsDeepestChildTreeSum(root, 0, &maxLevel, &sum)
	return sum
}

func dfsDeepestChildTreeSum(root *TreeNode, level int, maxLevel, sum *int) {
	if root == nil {
		return
	}
	if level > *maxLevel {
		*maxLevel, *sum = level, root.Data
	} else if level == *maxLevel {
		*sum += root.Data
	}
	dfsDeepestChildTreeSum(root.Left, level+1, maxLevel, sum)
	dfsDeepestChildTreeSum(root.Right, level+1, maxLevel, sum)
}

func main() {
	tn := &TreeNode{1, nil, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{3, nil, nil}}}
	res := deepestChildTreeSum(tn)
	fmt.Println(res)
}

//$ go run interview5-4.go
//7
